#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    auto build = [&](auto&& build, int begin, int end, int& u)->TreeNode* {
        if (begin > end) return nullptr;
        TreeNode* nnode = new TreeNode(preorder[u]);

        int i;
        for (i = begin; i <= end; i++)
            if (inorder[i] == preorder[u])
                break;
        u++;
        nnode->left = build(build, begin, i - 1, u);
        nnode->right = build(build, i + 1, end, u);
        return nnode;
    };

    int i = 0;
    return build(build, 0, preorder.size() - 1, i);
}

bool isValidBST(TreeNode* root) {
    auto dfs = [&](auto&& dfs, TreeNode* root, long long lower, long long upper)->bool {
        if (!root)   return true;
        if (root->val <= lower || root->val >= upper) return false;
        return dfs(dfs, root->left, lower, root->val) && dfs(dfs, root->right, root->val, upper);
    };

    return dfs(dfs, root, INT_MIN, INT_MAX);
}